A pixel image enhancement system for higher resolution black and white and color images including alphanumeric characters and graphic video game designs displayed on such devices such as computer monitors, printers, facsimile machines, television screens, video game displays, and the like.
A need for higher resolution image production is well documented in the art. A close inspection of letters and graphic images on a computer screen or a hard copy print out reveal jagged lines causing an unsightly rough appearance of displayed and printed images.
One method of ameliorating this problem, disclosed in U.S. Pat. No. 4,437,122 to the Xerox Corporation involves isolating a center pixel, matching the 3 by 3 pixel pattern surrounding and including the center pixel with a table of xe2x80x9cstandard pixel formatsxe2x80x9d, and then subdividing the center pixel area into enhanced xe2x80x9csubpixelsxe2x80x9d.
Another method utilizes pattern matching templates operating on a window with a central bit. See U.S. Pat. No. 4,847,641 assigned to the Hewlett Packard Corporation.
One disadvantage in the prior art is the use of xe2x80x9cstandard pixel formatsxe2x80x9d and templates. When the selected pixel and the surrounding pixels to be analyzed are few in number, for example a 3 by 3 pixel matrix, and when the pixels are only bi-valued (black or white), the total number of possible input patterns is small. A 3 by 3 matrix of input pixels, each either black or white, has a total of only 512 possible patterns which, in contemporary hardware or software can easily be handled by placing 512 hand selected xe2x80x9canswersxe2x80x9d (xe2x80x9ctemplatesxe2x80x9d or xe2x80x9cstandard pixel formatsxe2x80x9d) into a look-up table. The analysis of only a 3 by 3 pixel matrix is very error prone, however, since the pattern analyzed can be indicative of a line angled at 45xc2x0 or the beginning of a curve. Analyzing a larger subset of the input pixel matrix requires the formation of a very large unwieldy number of standard pixel formats or templates.
The templates disclosed in the Hewlett Packard patent are similar to input windows except for having a third pixel state in addition to black or white. The third state is called a xe2x80x9cdon""t carexe2x80x9d condition. This allows each template to represent many possible inputs specifically two to the power of the number of xe2x80x9cdon""t carexe2x80x9d conditions in a given template, thus greatly reducing the number of templates required. Such trivalued templates, however, are still very limited. For example, if one tiny feature is to be allowed two different ways, two completely separate templates are required.
Although it may be fairly straight forward to straighten out a jagged 45xc2x0 line according to this prior methodology, it is nearly impossible to use standard pixel formats or templates to account for the numerous possible permutations of angled lines, curves, and other features inherent in the display of alpha numeric characters and graphical displays. In addition, the prior art methodologies are generally constrained to bi-valued input bitmaps.
Another type of system involves the use of xe2x80x9canti-aliasingxe2x80x9d filters which are linear. Anti-aliasing filters do not make inferences based on real world properties of edges such as slope continuity. Anti-aliasing filters remove spurious a high frequency information which is an artifact of the quantization process but they do not replace the spurious high frequency information with inferred hypothetical high frequency information.
It is therefore an object of this invention to provide an improved pixel image enhancement system and methodology.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which is not constrained to templates or standard pixel formats.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which is not constrained by use of a center pixel, a center bit, or a small 3 by 3 input pixel pattern.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which eliminates the requirement that the input pixels be bi-valued.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which is able to handle any input pixel pattern and which enhances color images.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which is implemented in hardware instead of software thereby decreasing the processing time.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which can be used in conjunction with any type of output display device: CRT""s, LCD displays, printers, facsimile machines, television, and which is easily housed within a chip which can be located in the output device.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which employs an inferential algorithm for image outline detection.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which utilizes a digital modulator, in some applications, for precise pixel positioning.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which lowers the video subsystem cost.
It is a further object of this invention to provide such a pixel image enhancement system and methodology which lowers memory and processing requirements.
This invention results from the realization that a high resolution pixel image enhancement system can be accomplished, not by analyzing a central pixel of a small matrix of input pixels using templates or tables of standard pixel formats, but by detecting elemental edges between adjacent input pixels, generating an edge map, and using Boolean equations implemented in hardware to produce a segment of an inferred edge, within an output cell area, from the edge map resulting in higher resolution and accuracy than the inputted pixel map would otherwise allow. The result is a system which enhances color as well as black and white alphanumeric and graphic images and which can be used in conjunction with any type of display device: printers, CRTs, LCD displays, projection displays, television, facsimile machines and the like at a much lower cost. An unwieldy number of patterns or templates need not be designed and the system can be implemented on a chip which is placed in the output device or elsewhere for very high resolution.
This invention features a pixel image enhancement system and method. The system includes means, responsive to an input pixel map, for detecting edges between adjacent input pixels of the map. The edge may be defined by two adjacent pixels of different color. There are means for analyzing a set of pixels surrounding an output cell area partially overlapping a plurality of pixels including means for generating a case number characterizing the inferred edge based on the set of pixels surrounding the output cell. There are also means, responsive in the case number, for producing a display signal which drives an output device to display, to the best of its ability, the inferred edge.
In the preferred embodiment, the input pixel bit map is 640xc3x97480 pixels and the output device has a resolution of 800xc3x97600 pixels. The display signal is output for each pixel of the output device in the typical implementation. The system also features means for detecting an edge between adjacent pixels by identifying a difference of color between the adjacent input pixels. The means for generating a case number preferably includes a set of logic operations implementing Boolean equations defining the case number as a function of the set of pixels surrounding the detected edge. In a preferred embodiment, an edge map is generated which contains the detected edge.
This invention also features a pixel image enhancement system comprising means for creating an output cell which partially overlaps a plurality of adjacent input pixels, means for defining a window of input pixels surrounding the output cell, means for generating a case number characterizing the window and an inferred edge piece within the output cell, and means for displaying the output cell.
The means for detecting an edge between adjacent pixels includes means for identifying a difference of color between the adjacent input pixels. The input pixels are typically in the form of a pixel map and the means for creating an output cell includes means for sequentially creating output cells at each set of adjacent input pixels across scanned rows. The window typically includes an odd number of pixels in one direction and an even number of pixels in the other direction and in the current embodiment the window is 9xc3x9710 pixels. The means for generating the case number typically includes a set of logic operations implementing Boolean equations defining the case number as a function of the detected edges between adjacent pixels within the window. As an intermediate step, an edge map containing the detected edges is also generated.
This invention also features a pixel image enhancement method comprising the steps of detecting, in response to an input pixel map, an edge between adjacent input pixels in the map, analyzing a set of pixels surrounding the detecting edge including generating a case number of characterizing an inferred edge based on the set of pixels surrounding the detected edge, and producing a display signal, in response to the case number, which drives an output device to display the inferred edge.
The method of this invention typically includes the steps of detecting edges between adjacent input pixels, creating an output cell which partially overlaps a plurality of adjacent input pixels, defining a window of input pixels including the plurality of adjacent input pixels, generating a case number characterizing the window and an inferred edge within the output cell, and then displaying the output cell. The step of detecting an edge between the adjacent pixels typically includes identifying a difference of color between adjacent input pixels. The input pixels may be in the form of a bit map and if so the step of creating the output cells includes sequentially creating output cells at each set of adjacent input pixels in the bit map. The window typically includes an odd number of pixels in one direction and even number of pixels in the other direction such as a 9xc3x9710 window or an even number in both dimensions such as 8 by 8. The step of generating a case number includes implementing Boolean equations defining the case number as a function of the detected edges between adjacent pixels within the window. The method further includes a step of generating an edge map containing the detected edges.
The above system and method apply to both bivalued (e.g. black and white) and color images. For color images, this invention also features a computation device for converting a digitized source color image containing at least three different colors continuously disposed, into a second electronic color image of different effective spatial resolution. There are means for forming a scanned sequence of examination windows into the digitized color image. The examination windows are at least three pixels high and at least three pixels wide. There are also means for defining a corresponding scanned sequence of elemental inferral areas smaller than, and substantially centered within, the examination windows. There are means, responsive to the colors of pixels within the examination windows, for computing at least one inferred edge piece within at least some of said elemental inferral areas. There are also means for combining the inferred edge pieces within the elemental inferral areas, with the source image color to produce one elemental unit of the second electronic color image.
The second electronic color image typically comprises a standard array of binary coded pixels. The second color image may be formatted for display (printing) on a color printer, or for display on a color display device including a cathode ray tube or a fixed pixel flat-panel display. In some cases, the spatial resolution is a decreased resolution, and other cases, the spatial resolution is an increased resolution. The color display may be a multiresolution display operated in higher resolution mode than the resolution of the digitized color image. The computation device may comprise a microprocessor with software. The computation device may be a part of an integrated circuit including pipelined logic operable in real time. The digitized color image may be a still image or a moving color image.
The Examination window is typically rectangular and has an even number of pixels in one dimension and an odd number of pixels in the other dimension. It may also have an even number of pixels in both dimensions. The Examination window may be of variable size and may be elliptical, i.e. have its corners missing.
The elemental inferral area, in the preferred embodiment, is equal in area and aspect ratio to the input pixels in the digitized color image. It at least partially overlaps at least two adjacent input pixels in the digitized color image. The elemental inferral area may partially overlap four touching input pixels in the digitized color image.
The means for computing the inferred edge pieces typically computes either zero, one, or two inferred-edge pieces within a given elemental inferral-area. The computation selects from among a predefined set of no more than 1000 predefined inferred-edge pieces. The selection is usually represented as a binary case number. Alternatively, the selection may be represented as an active signal on one of a set of conductors, the set of conductors corresponding to the set of predefined inferred-edge pieces. The means for computing the inferred-edge pieces comprises means for separately computing unoriented inferred edge pieces and separately computing an orientation to be applied to the unoriented inferred-edge pieces. There may be four possible orientations constituting all possible combinations of vertical and horizontal mirror images of unoriented edge-pieces, or eight by further including 90xc2x0 rotation.
Further included are means for computing an intermediary map of existing edges in the digitized color image and within the examination window. The intermediary map of existing edges may designate an edge as present between two contiguous source pixels when the contiguous source pixels differ at all in color. The intermediary map of existing edges may designate an edge as present between two contiguous source pixels when the contiguous source pixels differ in color by more than a given threshold amount in units approximately representative of the psychological color difference between the pixels. The threshold may be dynamically optimized.
The two contiguous source pixels may be diagonally disposed with respect to each other and touching only at a shared corner. At least one scan line of the intermediary map of existing edges may be buffered in lieu of buffering at least one scan line of the digitized color image. The means for computing inferred edge pieces includes means for detecting near xe2x88x9245 edges in the digitized color image and means for detecting single-pixel width features in the digitized color image. The means for detecting single pixel width features includes means for approximately preserving the feature width in the inferred image. The means for selecting the inferred-edge pieces includes means for detecting the major subfeatures in the examination window shared by a plurality of candidate inferred-edge pieces.
There may be exactly two such subfeature detections combined to select the desired inferred-edge piece. The detection of a major subfeature may serve to inhibit selection of a particular inferred-edge piece. This inhibitory subfeature is typically a local checker board pattern of pixels in the examination window. The subfeature may also be a single pixel-sized typographic serif. It may also be a single pixel-sized typographic cross-stroke. The means for selecting the inferred-edge piece may include means for prioritizing among multiple inferred-edge piece candidates of a given orientation which would otherwise be selected. The computation of an inferred-edge piece requires that the source pixels along at least one side of the complete edge all have substantially the same color. There are means for estimating which of two diagonally-disposed features is continuous through a given node where the continuity is otherwise ambiguous. The computation further includes means for knowing that the detection criteria for a given unoriented inferred-edge piece are internally symmetric and means for suppressing the generation of any orientation which is rendered redundant by that symmetry. The computation of the inferred-edge pieces includes means for detecting curved edges which are tangent to one of the orientation axes. The computation computes inferred-edge pieces which approximately join end-to-end with the inferred edge-pieces in adjacent elemental inferral-areas. The computation of inferred-edge pieces also includes means for detecting double-size jags characteristic of sharply-curved edges tangent to a 45xc2x0 line. The computation of the inferred-edge pieces favors the longer complete inferred-edge in otherwise ambiguous situations. The inferred-edge piece may comprise at least one straight-line segment represented as a vector and/or may be represented as a uncolored bi-valued bit-map of much greater resolution than the digitized source color image. This bit-map may be generated in a run-length-encoded form. The vector or bit-map representation of the inferred-edge pieces is computed by using the case numbers to access a look-up table in one preferred embodiment.
The elemental unit of the second electronic color image may be a pulse of modulated width and position. This pulse may also be modulated in amplitude. The elemental unit of the second electronic color image may be a standard red-green-blue binary-encoded pixel.
The device of this invention further may include means for utilizing the predefined separate locations of the color sub-pixels in a fixed-pixel color display to increase effective luminance resolution. The elemental unit of the second electronic color image may be a standard cyan-magenta-yellow-black binary-encoded pixel. The means for combining inferred-edge pieces may include storage means for storing one previous scan line of computed elemental inferral areas. In some cases, the resolution of the digitized color image is the same as the nominal resolution of the final output device and elemental units of the second electronic color image are positioned on scan lines half-way between the scan lines of the computated elemental-inferral areas.
Finally, this invention features a computation method for converting a digitized source color image containing at least three different colors contiguously disposed. This digitized source color image is converted into a second electronic color image of different effective spatial resolution using a scanned sequence of examination windows into the digitized color image. The examination windows are at least three pixels high and at least three pixels wide. The method of this invention utilizes a scanned sequence of elemental inferral-areas smaller than, and substantially centered within, the examination windows. At least one inferred-edge piece is computed within at least some of the elemental inferral-areas in response to the detected edges within the examination windows. Then, the inferred edge piece(s) within the elemental inferred-areas is combined with color data from the source color image to produce one elemental unit of the second electronic color image.